package th.retrofit.lib;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class ArraySolution {

    /**
     * 下一个排列
     * 如12435
     * 下一个比它大的数字 12453
     * @param nums 存放数字的数组
     */
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        int i = length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]){
            i--;
        }
        int j = length - 1;
        if (i >= 0) {
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    /**
     * 搜索旋转数组
     * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
     * @param nums 经k位置旋转后的数组
     * @param target 查找值
     * @return 查找值所在位置
     */
    public int search(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return -1;
        }
        if (length == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = length - 1;
        while (l <= r) {
            int middle = (r + l) / 2;
            if (nums[middle] == target) {
                return middle;
            }
            if (nums[0] <= nums[middle]) {
                if (nums[0] <= target && target < nums[middle]) {
                    r = middle - 1;
                } else {
                    l = middle + 1;
                }
            } else {
                if (nums[middle] < target && target <= nums[length - 1]) {
                    l = middle + 1;
                } else {
                    r = middle - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
     * @param nums 一个按照升序排列的整数数组
     * @param target 一个目标值
     * @return 给定目标值在数组中的开始位置和结束位置
     */
    public int[] searchRange(int[] nums, int target) {
        int lIndex = binarySearch(nums, target, true);
        int rIndex = binarySearch(nums, target, false) - 1;
        if (lIndex <= rIndex && rIndex < nums.length && nums[lIndex] == target && nums[rIndex] == target) {
            return new int[]{lIndex, rIndex};
        } else {
            return new int[]{-1, -1};
        }
    }

    private int binarySearch(int[] nums, int target, boolean lower) {
        int answer = nums.length, left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                answer = mid;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }

    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     * https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
     * @param nums 一个按照升序排列的整数数组
     * @param target 一个目标值
     * @return 给定目标值在数组中的开始位置和结束位置
     */
    public int[] searchRange1(int[] nums, int target) {
        int lIndex = binarySearchLess(nums, target) + 1;
        int rIndex = binarySearchGreater(nums, target) - 1;
        if (lIndex <= rIndex && lIndex >= 0 && rIndex < nums.length && nums[lIndex] == target && nums[rIndex] == target) {
            return new int[]{lIndex, rIndex};
        } else {
            return new int[]{-1, -1};
        }
    }

    // 找到第一个小于target的值
    private int binarySearchLess(int[] nums, int target) {
        int result = -1, l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] < target) {
                result = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return result;
    }

    //找到第一个大于target的值
    private int binarySearchGreater(int[] nums, int target) {
        int result = nums.length, l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] > target) {
                result = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return result;
    }

    /**
     * 组合总和
     * https://leetcode-cn.com/problems/combination-sum/
     * @param candidates 一个无重复元素的正整数数组candidates
     * @param target 一个正整数target
     * @return candidates中所有可以使数字和为目标数target的唯一组合
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new LinkedList<>();
        List<Integer> combine = new LinkedList<>();
        backstack(candidates, target, results, combine, 0);
        return results;
    }

    private void backstack(int[] candidates, int target, List<List<Integer>> results,
                           List<Integer> combine, int index) {
        if (index == candidates.length) return;
        if (target == 0) {
            results.add(new LinkedList<>(combine));
            return;
        }
        backstack(candidates, target, results, combine, index + 1);
        if (target - candidates[index] >= 0) {
            combine.add(candidates[index]);
            backstack(candidates, target - candidates[index], results, combine, index);
            combine.remove(combine.size() - 1);
        }
    }

    /**
     * 组合总和
     * https://leetcode-cn.com/problems/combination-sum/
     * @param candidates 一个无重复元素的正整数数组candidates
     * @param target 一个正整数target
     * @return candidates中所有可以使数字和为目标数target的唯一组合
     */
    public List<List<Integer>> combinationSum0(int[] candidates, int target) {
        List<List<Integer>> results = new LinkedList<>();
        List<Integer> combine = new LinkedList<>();
        backstack0(candidates, target, results, combine, 0);
        return results;
    }

    private void backstack0(int[] candidates, int target, List<List<Integer>> results,
                           List<Integer> combine, int index) {
        if (target < 0) return;
        if (target == 0) {
            results.add(new LinkedList<>(combine));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            combine.add(candidates[i]);
            backstack0(candidates, target - candidates[i], results, combine, i);
            combine.remove(combine.size() - 1);
        }
    }

    /**
     * 组合总和
     * https://leetcode-cn.com/problems/combination-sum/
     * @param candidates 一个无重复元素的正整数数组candidates
     * @param target 一个正整数target
     * @return candidates中所有可以使数字和为目标数target的唯一组合， 每个数字可以无限使用
     */
    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        List<List<Integer>>[] dp = new List[target + 1];
        for (int i = 0; i < target + 1; i ++) {
            dp[i] = new LinkedList<>();
        }
        for (int i = 0; i <= target; i++) {
            int cLen = candidates.length;
            for (int j = 0; j < cLen; j++) {
                if (i - candidates[j] == 0 ) {
                    List<Integer> temp = new LinkedList<>();
                    temp.add(candidates[j]);
                    List<List<Integer>> pre = dp[i];
                    pre.add(temp);
                } else if (i - candidates[j] > 0) {
                    List<List<Integer>> pre = dp[i - candidates[j]];
                    if (pre != null) {
                        for (List<Integer> item : pre) {
                            LinkedList<Integer> child = new LinkedList<>(item);
                            child.add(candidates[j]);
                            boolean isExisted = false;
                            for (List<Integer> source: dp[i]) {
                                if (isListEqual(source, child)) {
                                    isExisted = true;
                                    break;
                                }
                            }
                            if (!isExisted) {
                                dp[i].add(child);
                            }
                        }
                    }
                }
            }

        }
        return dp[target];
    }

    private boolean isListEqual(List<Integer> source, List<Integer> target) {
        List<Integer> copied = new LinkedList<>(source);
        for (Integer num : target) {
            copied.remove(num);
        }
        return copied.isEmpty();
    }

    /**
     * 组合总和
     * https://leetcode-cn.com/problems/combination-sum-ii/
     * @param candidates 一个无重复元素的正整数数组candidates
     * @param target 一个正整数target
     * @return candidates中所有可以使数字和为目标数target的唯一组合, 每个数字仅能使用一次
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> results = new LinkedList<>();
        List<Integer> combine = new LinkedList<>();
        dfs(candidates, target, results, combine, 0);
        return results;
    }

    private void dfs(int[] candidate, int target, List<List<Integer>> results,
                     List<Integer> combine, int index) {
        if (target < 0) return;
        if (target == 0) {
            results.add(new LinkedList<>(combine));
            return;
        }

        for (int i = index; i < candidate.length; i++) {

            //横向去重
            if (i - 1 >= index && candidate[i] == candidate[i - 1]) {
                continue;
            }
            combine.add(candidate[i]);
            dfs(candidate, target - candidate[i], results, combine, i + 1);
            combine.remove(combine.size() - 1);
        }
    }

    /**
     * 全排列
     * https://leetcode-cn.com/problems/permutations/
     * @param nums 不含重复数字的数组 nums
     * @return 所有可能的全排列
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        permute(nums, results, 0);
        return results;
    }

    public void permute(int[] nums, List<List<Integer>> results, int start) {
        int length = nums.length;
        if (start >= length) return;
        if (start == length - 1) {
            List<Integer> list = new ArrayList<>();
            list.add(nums[start]);
            results.add(list);
            return;
        }
        permute(nums, results, start + 1);
        int size = results.size();
        for (int i = 0; i < size; i++) {
            List<Integer> children = results.get(i);
            int cSize = children.size();
            for (int j = 0; j <= cSize; j++) {
                if (j != children.size()) {
                    List<Integer> temp = new ArrayList<>(children);
                    temp.add(j, nums[start]);
                    results.add(temp);
                } else {
                    children.add(j, nums[start]);
                }
            }
        }
    }

    /**
     * 全排列
     * https://leetcode-cn.com/problems/permutations/
     * @param nums 不含重复数字的数组 nums
     * @return 所有可能的全排列
     */
    public List<List<Integer>> permute1(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> child = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        permuteBacktrack(nums, results, child, used, 0);
        return results;
    }

    private void permuteBacktrack(int[] nums, List<List<Integer>> results,
                                  List<Integer> child, boolean[] used, int index) {
        if (index == nums.length) {
            results.add(new ArrayList<>(child));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                child.add(nums[i]);
                permuteBacktrack(nums, results, child, used, index + 1);
                child.remove(Integer.valueOf(nums[i]));
                used[i] = false;
            }
        }
    }

    /**
     * 全排列
     * https://leetcode-cn.com/problems/permutations-ii/
     * @param nums 含重复数字的数组 nums
     * @return 所有可能的全排列, 不能出现相同的排列
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> child = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        permuteUniqueBacktrack(nums, results, child, used, 0);
        return results;
    }

    private void permuteUniqueBacktrack(int[] nums, List<List<Integer>> results,
                                  List<Integer> child, boolean[] used, int index) {
        if (index == nums.length) {
            results.add(new ArrayList<>(child));
            return;
        }
        int pre = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (pre != nums[i] && !used[i]) {
                used[i] = true;
                child.add(nums[i]);
                permuteUniqueBacktrack(nums, results, child, used, index + 1);
                child.remove(Integer.valueOf(nums[i]));
                used[i] = false;
                pre = nums[i];
            }
        }
    }

    public static void main(String[] args) {
//        int[] nums = {10,1,2,7,6,1,5};
        int[] nums = {1, 2 ,3};
        new ArraySolution().permute(nums);
//        new ArraySolution().nextPermutation(nums);
//        for (int num : nums) {
//            System.out.println(num);
//        }

//        System.out.println(new ArraySolution().binarySearchGreater(nums, 3));
//        Arrays.stream(new ArraySolution().searchRange1(nums, 1)).forEach(System.out::println);
//        new ArraySolution().permuteUnique(nums).forEach(it -> {
//            it.forEach(System.out::print);
//            System.out.println();
//        });
    }
}
